package main.leetcode.primary.from701to800;

import main.datastruc.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 783. 二叉搜索树节点最小距离
 *
 * <p>给定一个二叉搜索树的根节点 root，返回树中任意两节点的差的最小值。
 *
 * <p>注意：<br>
 * 二叉树的大小范围在 2 到 100。 <br>
 * 二叉树总是有效的，每个节点的值都是整数，且不重复。 <br>
 *
 * @see main.leetcode.clockin.October.day12 递归解法
 */
public class ex783 {
    public static void main(String[] args) {
        System.out.println(
                new ex783().minDiffInBST(TreeNode.creCmpBTree(new int[] {5, 3, 7, 1, 4, 6, 8})));
    }

    public int minDiffInBST(TreeNode root) {
        int res = Integer.MAX_VALUE;
        TreeNode pre = null;
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.poll();
                if (pre != null) {
                    res = Math.min(res, node.val - pre.val);
                }
                pre = node;
                node = node.right;
            }
        }
        return res;
    }
}
